package BFS_DFS;

//    public static int dfs(int step){
//        if(当前状态=目标状态){
//            return ...;
//        }
//        for(查找新状态){
//            标记状态;
//            dfs(step+1);
//            撤销状态标记，也就是回溯;
//        }
//    }

class TreeNode{
    int value;//节点值
    TreeNode left;//左子节点
    TreeNode right;//右子节点
    TreeNode(int value){
        this.value=value;
        left=null;
        right=null;
    }
}

public class DFS {
    public static void main(String[] args) {
        /*
                1
               / \
              2   3
             / \
            4   5
        */
        TreeNode root=new TreeNode(1);
        root.left=new TreeNode(2);
        root.right=new TreeNode(3);
        root.left.left=new TreeNode(4);
        root.left.right=new TreeNode(5);

        System.out.println("前序遍历：");
        preorderTraversal(root); // 输出: 1 2 4 5 3
        System.out.println("\n中序遍历：");
        inorderTraversal(root); // 输出: 4 2 5 1 3
        System.out.println("\n后序遍历：");
        postorderTraversal(root); // 输出: 4 5 2 3 1
    }

    //前序遍历
    public static void preorderTraversal(TreeNode node) {
        if(node==null) return;
        System.out.print(node.value);//访问根节点
        preorderTraversal(node.left);//遍历左子树
        preorderTraversal(node.right);//遍历右子树
    }

    //中序遍历
    public static void inorderTraversal(TreeNode node) {
        if(node==null) return;
        preorderTraversal(node.left);//遍历左子树
        System.out.print(node.value);//访问根节点
        preorderTraversal(node.right);//遍历右子树
    }

    //后序遍历
    public static void postorderTraversal(TreeNode node) {
        if(node==null) return;
        preorderTraversal(node.left);//遍历左子树
        preorderTraversal(node.right);//遍历右子树
        System.out.print(node.value);//访问根节点
    }
}
